package com.leetcode.partition1;

import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/8/14 8:47
 */
public class LC93复原IP地址 {

    public static List<String> restoreIpAddresses(String s) {
        List<String> answer = new ArrayList<>();
        if (s.length() < 4 || s.length() > 12) return answer;
        backtracking(answer, 0, 0, s);
        return answer;
    }

    public static void main(String[] args) {
        String str = "101023";
//        System.out.println(str.substring(0, 1));
        System.out.println(restoreIpAddresses(str));
    }

    private static void backtracking(List<String> answer, int startIndex, int pointCount, String str) {
        if (pointCount == 3) {
            if (isValid(str) && !answer.contains(str)) answer.add(str);
            return;
        }
        for (int i = startIndex; i < str.length(); i++) {
            if (i == 0 || str.charAt(i - 1) == '.') continue;
            backtracking(answer, startIndex + 2,  pointCount + 1, str.substring(0, i) + "." + str.substring(i));
        }
    }

    private static boolean isValid(final String s) {
        String[] arr = s.split("\\.");
        if (arr.length != 4) return false;
        for (String item : arr) {
            if (item.length() > 3 || item.length() == 0) return false;
            int num = Integer.parseInt(item);
            if (num < 0 || num > 255) return false;
            if (item.length() > 1 && item.charAt(0) == '0') return false;
        }
        return true;
    }
}
